#include <iostream>
#include <iomanip>
using namespace std;

void Floyd(int* g, int n)
{
	int i;
	int* eccentricity = new int[n],
		* pathNum = new int[n * n];
	if (!eccentricity || !pathNum)
	{
		cout << "内存申请错误！" << endl;
		exit(1);
	}

	for (i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (*(g + i * n + j) == -1)
			{
				*(g + i * n + j) = 2 ^ 31 - 1;
			}
			*(pathNum + i * n + j) = *(g + i * n + j);
		}
	}

	for (i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{

				if (*(pathNum + j * n + i) + *(pathNum + i * n + k) < *(pathNum + j * n + k))
				{
					*(pathNum + j * n + k) = *(pathNum + j * n + i) + *(pathNum + i * n + k);
				}
			}
		}
	}

	for (i = 0; i < n; i++)
	{
		int max = 0;
		for (int j = 0; j < n; j++)
		{
			if (*(pathNum + j * n + i) > max)
			{
				max = *(pathNum + j * n + i);
			}
		}
		if (max == (2 ^ 31 - 1))
		{
			max = -1;
		}
		*(eccentricity + i) = max;
	}

	cout << endl;
	for (i = 0; i < n; i++)
	{
		cout << *(eccentricity + i) << " ";
	}
	cout << endl;

	delete[] eccentricity;
	delete[] pathNum;
}

int main()
{
	int order;
	cin >> order;

	int* AdjMatrix = new int[order * order];
	if (!AdjMatrix)
	{
		cout << "内存申请错误！" << endl;
		return 1;
	}

	int i;
	for (i = 0; i < order; i++)
	{
		for (int j = 0; j < order; j++)
		{
			cin >> *(AdjMatrix + i * order + j);
		}
	}

	Floyd(AdjMatrix, order);
	delete[] AdjMatrix;
	system("pause");
	return 0;
}